//
// Description: 92. 反转链表 II
// Created by Loading on 2022/5/1.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

ListNode *reverseBetween(ListNode *head, int left, int right) {
    // 定义一个头结点辅助
    auto hair = new ListNode;
    hair->next = head;
    // pre 为反转区域的前一个节点，tail 为反转区域的后一个节点
    auto pre = hair, tail = hair;
    int n = right - left + 1;
    int index = 1;
    while (index < right) {
        if (index < left) {
            pre = pre->next;
        }
        tail = tail->next;
        ++index;
    }
    tail = tail->next->next;
    // node 为要反转的节点
    auto node = pre->next;
    while (n) {
        auto next = node->next;
        node->next = tail;
        tail = node;
        node = next;
        --n;
    }
    // 链表衔接
    pre->next = tail;
    head = hair->next;
    // 防止内存泄漏
    delete hair;

    return head;
}

int main() {
    vector<int> nums{1, 2, 3, 4, 5};
    auto head = generateListNode(nums);
    int left = 2;
    int right = 4;
    auto res = reverseBetween(head, left, right);
    cout << printfListNode(res) << endl;

    return 0;
}